package com.tgy.leetcode;

import java.util.Arrays;

/**
 * @Author: tgy
 * @Date: 12/9/20 11:34 AM
 *
 * https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock-iii/
 */
public class _123_买卖股票的最佳时机_III_01 {

    public int maxProfit(int[] prices) {

        if (prices == null || prices.length <= 1) {

            return 0;
        }

        int max = 0;

        int len = prices.length;

        int sum;
        for (int i = 0; i < prices.length; i++) {

            sum = subPartMaxProfit(prices,0,i) + subPartMaxProfit(prices,i,len);
            max = Math.max(max,sum);
        }

        return max;
    }

    private int subPartMaxProfit(int[] prices,int start, int end) {

        int min = prices[start];

        int profitMax = 0;
        for (int i = start+1; i < end; i++) {

            if (prices[i] < min) {

                min = prices[i];
            }

            profitMax = Math.max(profitMax,prices[i] -min);
        }

        return profitMax;
    }
}
